package com.coder.algorithm.offer_2;

import java.util.Arrays;
import java.util.Locale;

/**
 * 矩阵中的路径
 *
 * @author yuhushuan
 * @date 2020/6/9 11:20
 */
public class _12_1_StringPathInMatrix {
    static boolean log = false;

    public static void main(String[] args) {
        char[][] matrix = null;
        String str = null;

        // 功能测试（在多行多列的矩阵中存在或者不存在路径）
        matrix = new char[][]{
                {'a', 'b', 't', 'g'},
                {'c', 'f', 'c', 's'},
                {'j', 'd', 'e', 'h'}
        };
        print(matrix, "bfce");
        print(matrix, "bat");

        // 边界值测试（矩阵只有一行或者只有一列；矩阵和路径中的所有字母都是相同的）
        print(new char[][]{{'a', 'b', 't', 'g'}}, "bfce");

        matrix = new char[][]{
                {'a', 'a', 'a', 'a'},
                {'a', 'a', 'a', 'a'},
                {'a', 'a', 'a', 'a'}
        };

        print(matrix, "abcd");

        // 特殊输入测试（null）
        print(null, "abcd");
        print(matrix, null);
    }

    private static void print(char[][] matrix, String str) {
        printMatrix(matrix);
        if (matrix == null) {
            System.out.println(String.format(Locale.getDefault(),
                    "存在路径 \"%s\" 为：%b",
                    str, hasPath(matrix, 0, 0, str)));
        } else {
            System.out.println(String.format(Locale.getDefault(),
                    "存在路径 \"%s\" 为：%b",
                    str, hasPath(matrix, matrix.length, matrix[0].length, str)));
        }
        System.out.println();
    }

    private static void printMatrix(char[][] matrix) {
        System.out.println("矩阵：");
        if (matrix == null) {
            System.out.println("null");
            return;
        }
        for (int i = 0; i < matrix.length; ++i) {
            System.out.println(Arrays.toString(matrix[i]));
        }
    }

    private static boolean hasPath(char[][] matrix, int rows, int cols, String str) {
        if (matrix == null || rows < 1 || cols < 1 || str == null) {
            return false;
        }
        // 创建和字符串矩阵一样大小的 boolean 矩阵标识路径是否已经进入了每个格子
        boolean[][] visited = new boolean[rows][cols];
        int pathLength = 0;
        // 尝试从任何一点出发，是否存在路径
        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (log) {
                    System.out.println("row = " + row + " col = " + col);
                }
                if (hasPathCore(matrix, rows, cols, row, col, str, pathLength, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean hasPathCore(char[][] matrix, int rows, int cols, int row, int col,
                                       String str, int pathLength, boolean[][] visited) {
        if (str.length() == pathLength) {
            return true;
        }

        boolean hasPath = false;
        if (log && row >= 0 && row < rows && col >= 0 && col < cols) {
            System.out.println(String.format(Locale.getDefault(), "row=%d; col=%d; len=%d, char='%c' matrix='%c'",
                    row, col, pathLength, str.charAt(pathLength), matrix[row][col]));
        }
        // 当前节点正好为字符串第 pathLength 位置的值
        if (row >= 0 && row < rows && col >= 0 && col < cols
                && matrix[row][col] == str.charAt(pathLength)
                && !visited[row][col]) {
            ++pathLength;
            visited[row][col] = true;

            hasPath = hasPathCore(matrix, rows, cols, row, col - 1, str, pathLength, visited)
                    || hasPathCore(matrix, rows, cols, row, col + 1, str, pathLength, visited)
                    || hasPathCore(matrix, rows, cols, row - 1, col, str, pathLength, visited)
                    || hasPathCore(matrix, rows, cols, row + 1, col, str, pathLength, visited);

            if (!hasPath) {// 下一个节点不匹配，回溯到上一节点
                --pathLength;
                visited[row][col] = false;
            }
        }
        return hasPath;
    }
}
